package com.alex.algorithm.medium;

import com.google.common.collect.Lists;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class Permutation {

    public static void main(String[] args) {
        List<Integer> nums = new ArrayList<>();
        nums.add(1);
        nums.add(2);
        nums.add(3);
        int j = 1;
        for (LinkedList<Integer> array : permute(nums)) {

            for (Integer i : array) {
                System.out.println(i);
            }
            System.out.println((j++) + "-----\n");
        }
    }

    private static ArrayList<LinkedList<Integer>> permute(List<Integer> nums) {
        LinkedList<Integer> list = new LinkedList();
        ArrayList<LinkedList<Integer>> permutatedList = new ArrayList<LinkedList<Integer>>();
        backtrack(permutatedList, list, nums);
        return permutatedList;
    }

    private static void backtrack(ArrayList<LinkedList<Integer>> permutatedList,
                                  LinkedList<Integer> list, List<Integer> nums) {
        if (list.size() == nums.size()) {
            permutatedList.add(Lists.newLinkedList(list));
            return;
        }
        for (int i = 0; i < nums.size(); ++i) {
            if (list.contains(nums.get(i))) continue;
            list.push(nums.get(i));
            backtrack(permutatedList, list, nums);
            list.pop();
        }
    }
}
